#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include "utils.h"
using namespace std;

class Solution {
public:
    TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder){
        if (!postorder.size() || !inorder.size()) return NULL;
        TreeNode *root = new TreeNode(postorder.back());
        vector<int>::iterator it = find(inorder.begin(), inorder.end(), postorder.back());
        int len = it - inorder.begin();
        root->left = build(postorder.begin(), postorder.begin()+len, inorder.begin(), it);
        root->right = build(postorder.begin()+len, postorder.end()-1, it+1, inorder.end());
        return root;
    }

    TreeNode *build(vector<int>::iterator post_beg, vector<int>::iterator post_end, vector<int>::iterator in_beg, vector<int>::iterator in_end){
        if (post_beg == post_end) return NULL;
        TreeNode *root = new TreeNode(*(post_end-1));
        vector<int>::iterator it = find(in_beg, in_end, *(post_end-1));
        int len = it - in_beg;
        root->left = build(post_beg, post_beg+len, in_beg, it);
        root->right = build(post_beg+len, post_end-1, it+1, in_end);
        return root;
    }
};

int main(int argc, char *argv[])
{
    int post[] = {4,5,2,7,6,8,3,1}, in[] = {4,2,5,1,6,7,3,8};
    vector<int> postorder(post, post+sizeof(post)/sizeof(int));
    vector<int> inorder(in,in+sizeof(in)/sizeof(int));

    Solution ss;
    print_vector(levelOrder(ss.buildTree(inorder, postorder)));

    return 0;
}
